#include <iostream>
#include <vector>

using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

//  没有恢复现场。
class Solution {
public:
    vector<vector<int>> ans;

    void dfs(TreeNode* root, vector<int> &path, int cur, int targetSum){
        if (!root) {
            if (cur == targetSum) ans.push_back(path);
            return;
        }  

        path.push_back(root->val);
        dfs(root->left, path, cur + root->val, targetSum);
        path.pop_back();

        path.push_back(root->val);
        dfs(root->right, path, cur + root->val, targetSum);
        path.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int> path;
        dfs(root, path, 0, targetSum);

        return ans;
    }
};

// 测试函数
int main() {
    // 构造测试二叉树
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(4);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(11);
    root->left->left->left = new TreeNode(7);
    root->left->left->right = new TreeNode(2);
    root->right->left = new TreeNode(13);
    root->right->right = new TreeNode(4);
    root->right->right->left = new TreeNode(5);
    root->right->right->right = new TreeNode(1);

    Solution sol;
    vector<vector<int>> res = sol.pathSum(root, 22);

    // 输出结果
    for (const auto &vec : res) {
        for (int x : vec) cout << x << " ";
        cout << endl;
    }

    return 0;
}
